package itheima.translate;

public class MortonCode {
    public static String encode(int row, int col) {
        // 转换为二进制字符串，去掉前缀 "0b"
        String rowBinary = Integer.toBinaryString(row);
        String colBinary = Integer.toBinaryString(col);

        // 确保两个二进制字符串长度相同，短的前面补零
        int maxLength = Math.max(rowBinary.length(), colBinary.length());
        rowBinary = padWithLeadingZeros(rowBinary, maxLength);
        colBinary = padWithLeadingZeros(colBinary, maxLength);

        // 按照规则构建莫顿码：列右、行右、列次右、行次右...
        StringBuilder mortonCode = new StringBuilder();
        for (int i = maxLength - 1; i >= 0; i--) {
            mortonCode.append(colBinary.charAt(i));  // 先取列的第i位（从右往左）
            mortonCode.append(rowBinary.charAt(i));  // 再取行的第i位（从右往左）
        }


        return mortonCode.reverse().toString();
    }

    public static int[] decode(String mortonCode) {
        // 检查码表长度是否为偶数
        if (mortonCode.length() % 2 != 0) {
            throw new IllegalArgumentException("莫顿码长度必须为偶数");
        }

        // 分离出行和列的二进制位
        StringBuilder rowBits = new StringBuilder();
        StringBuilder colBits = new StringBuilder();

        for (int i = 0; i < mortonCode.length(); i++) {
            if (i % 2 == 0) {
                // 偶数位置是列的位（原始顺序是从右到左的）
                rowBits.append(mortonCode.charAt(i));
            } else {
                // 奇数位置是行的位（原始顺序是从右到左的）
                colBits.append(mortonCode.charAt(i));
            }
        }

        // 反转字符串，恢复正确的二进制顺序
        rowBits.reverse();
        colBits.reverse();

        // 移除后导零
        String rowStr = removeTrailingZeros(rowBits.toString());
        String colStr = removeTrailingZeros(colBits.toString());


        System.out.println("行：" + rowStr);
        System.out.println("列：" + colStr);

        // 转换为十进制整数
        int row = Integer.parseInt(rowStr.toString(), 2);
        int col = Integer.parseInt(colStr.toString(), 2);

        return new int[]{row, col};
    }

    /**
     * 注意点：在二进制字符串前面补零，使其达到指定长度
     */
    private static String padWithLeadingZeros(String binaryStr, int length) {
        if (binaryStr.length() >= length) {
            return binaryStr;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length - binaryStr.length(); i++) {
            sb.append('0');
        }
        sb.append(binaryStr);
        return sb.toString();
    }

    private static String removeTrailingZeros(String binaryStr) {
        if (binaryStr == null || binaryStr.isEmpty()) {
            return "0";
        }
        int lastNonZero = binaryStr.length() - 1;
        // 从最后一位向前找第一个不是0的位置
        while (lastNonZero >= 0 && binaryStr.charAt(lastNonZero) == '0') {
            lastNonZero--;
        }
        // 全是0的情况
        if (lastNonZero < 0) {
            return "0";
        }
        // 截取到最后一个非零字符
        return binaryStr.substring(0, lastNonZero + 1);
    }
}

